package SwordOffer;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Sword_Offer_16 {

    public double myPow(double x, int n) {
        if (n == 0) {
            return 1.0;
        }
        boolean flag = n > 0;
        n = Math.abs(n);
        double res = x;
        n--;
        int nums = 1;
        Map<Integer, Double> map = new HashMap<>();
        map.put(1, x);

        while (n > 0) {
            if (nums <= n) {
                res *= res;
                n -= nums;
                nums <<= 1;
                map.put(nums, res);
            } else {
                int floor = floor(n);
                Double val = map.get(floor);
                res *= val;
                n -= floor;
                nums += floor;
            }
        }
        return flag ? res : 1 / res;
    }

    private int floor(int num) {
        int count = 0;
        while (num > 1) {
            count++;
            num >>= 1;
        }
        return 1 << count;
    }

    public static void main(String[] args) {
        Sword_Offer_16 model = new Sword_Offer_16();

        System.out.println(model.myPow(10.0, -2));
        System.out.println(model.myPow(2.0, 10));
        System.out.println(model.myPow(1.0, 2147483647));
    }
}
